%!TEX program = xelatex
%!TEX encoding = UTF-8 Unicode

\documentclass[10pt,a4paper]{article} 

\usepackage{ctex} % 中文支持
\usepackage[top=2.5cm, bottom=2.5cm, left=2.5cm, right=2.5cm]{geometry} % 页边距
\usepackage{amsmath, amssymb} % 数学公式与符号
\usepackage{graphicx}

\usepackage{pythonhighlight}
\usepackage{url} 

\usepackage{tikz}
\usetikzlibrary{graphs,arrows.meta}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 使表格美观
\usepackage{array}
\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
%\newcolumntype{N}{@{}m{0pt}@{}}
\setlength\extrarowheight{3pt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{titling}
\setlength{\droptitle}{-2cm} % 标题上移

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%文档的题目、作者与日期
\author{五六七 }
\title{村庄建小学选址 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

\begin{abstract}
几个村庄要一起建一所医院和一所小学，选在哪个地方比较方便。
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setcounter{tocdepth}{2}
%\renewcommand\contentsname{目录}
%
%\renewcommand {\baselinestretch} {1.3}\normalsize 
%\tableofcontents 
%\renewcommand {\baselinestretch} {1.0}\normalsize


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{问题描述}
有六个村庄，相互之间的距离如图所示。

\begin{center}
\begin{tikzpicture}[auto]

\node [circle,draw] (s1) at (0,0) {1}; 
\node [circle,draw] (s2) at (3,1) {2}; 
\node [circle,draw] (s3) at (3,-1) {3}; 
\node [circle,draw] (s4) at (6,1) {4}; 
\node [circle,draw] (s5) at (6,-1) {5}; 
\node [circle,draw] (s6) at (9,0) {6}; 

\draw (s1) to node {2} node [swap]{} (s2);
\draw (s1) to node {} node [swap]{7} (s3);
\draw (s2) to node {4} node [swap]{} (s3);
\draw (s2) to node {6} node [swap]{} (s4);
\draw (s2) to node {1} node [swap]{} (s5);
\draw (s3) to node {} node [swap]{8} (s4);
\draw (s3) to node {} node [swap]{3} (s5);
\draw (s4) to node {1} node [swap]{} (s5);
\draw (s4) to node {6} node [swap]{} (s6);
\draw (s5) to node {} node [swap]{3} (s6);

%\graph {(s1) -- (s2)};
%\graph {(s1) -- (s3)};
%\graph {(s2) -- (s3)};
%\graph {(s2) -- (s4)};
%\graph {(s2) -- (s5)};
%\graph {(s3) -- (s4)};
%\graph {(s3) -- (s5)};
%\graph {(s4) -- (s5)};
%\graph {(s4) -- (s6)};
%\graph {(s5) -- (s6)};

\end{tikzpicture}
\end{center}

各村的小学生人数如表所示。
\begin{table}[ht]
\centering
%\caption{各村小学生人数}
\begin{tabular}{|M{1.5cm}|M{0.8cm}|M{0.8cm}|M{0.8cm}|M{0.8cm}|M{0.8cm}|M{0.8cm}|} \hline 
村庄 & v1 & v2 & v3 & v4 & v5 & v6 \\ \hline 
小学生 & 50 & 40 & 60 & 20 & 70 & 90 \\ \hline 
\end{tabular}
\end{table}

现在计划建造一所医院和一所小学。
\begin{enumerate}
\item  医院建在哪个村庄，使得最远村庄的人到医院看病所走的路最短？
\item  小学建在哪个村庄，使得所有学生上学走的总路程最短？
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{建立模型}
基本思路是穷举法。设医院建在第一个村庄，然后计算第一个村庄与其它所有村庄的距离，从中求出最大值。
然后设医院建在第二个村庄，然后计算第二个村庄与其它所有村庄的距离，从中求出最大值。
最后在医院选址的所有可能中，求出所有最大值的最小值。这就是医院的最佳选址。
为此，我们要求出任意两个村庄之间的最短距离。

使用Floyd算法，可以方便地求出边上带权重的图中任意两个顶点之间的最短距离。
首先写出邻接矩阵。如果两个顶点 $v_i$ 与 $v_j$ 之间有边直接连接，那么邻接矩阵的第 $(i,j)$ 元素为这条边的权重，这里就是这两个村庄之间的距离。如果两个顶点之间没有直接的边相连，那么这个位置的元素为无穷大。
\begin{eqnarray}
W= \begin{pmatrix}
0&2&7&\infty&\infty&\infty \\ 
2&0&4&6&8&\infty \\ 
7&4&0&1&3&\infty \\ 
\infty&6&1&0&1&6 \\ 
\infty&8&3&1&0&3 \\ 
\infty&\infty&\infty&6&3&0 \\ 
\end{pmatrix}. 
\end{eqnarray}
注意到邻接矩阵是对称矩阵，而且对角线的元素都是零。

Floyd算法的基本思路是从邻接矩阵出发，构造一系列同样大小的矩阵。
记第零个矩阵 $A_0$ 就是邻接矩阵 $W$. 
第一个矩阵 $A_1$ 从 $A_0$ 构造。通过第1个顶点作为中间点，如果能够使得另外两个顶点之间的矩阵变小，则更新这两个顶点之间的最短矩阵。也就是说，矩阵 $A_1$ 的第 $(i,j)$ 元素为
\begin{eqnarray}
A_1(i,j) = \min \left(A_0(i,j), A_0(i,1)+A_0(1,j)  \right). 
\end{eqnarray}
可以预见的是，矩阵 $A_1$ 的元素基本上和 $A_0$ 的元素是一样的。

然后第二个矩阵 $A_2$ 从 $A_1$ 构造。通过第2个顶点作为中间点，更新矩阵 $A_1$. 使用的公式为 
\begin{eqnarray}
A_2(i,j) = \min \left(A_1(i,j), A_1(i,2)+A_1(2,j)  \right). 
\end{eqnarray}
最后我们得到第六个矩阵 $A_6$, 这是从 $A_5$ 出发，通过第6个顶点作为中间点，更新得到的矩阵。使用的公式为 
\begin{eqnarray}
A_6(i,j) = \min \left(A_5(i,j), A_5(i,6)+A_5(6,j)  \right). 
\end{eqnarray}
这样得到的矩阵 $A_6$ 的元素就是这六个顶点的两两之间的最短距离。



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{编程计算}

首先我们输入邻接矩阵。
\begin{python}
import numpy as np
R1=[0,2,7,np.inf,np.inf,np.inf]
R2=[2,0,4,6,8,np.inf]
R3=[7,4,0,1,3,np.inf]
R4=[np.inf,6,1,0,1,6]
R5=[np.inf,8,3,1,0,3]
R6=[np.inf,np.inf,np.inf,6,3,0]
W=np.array([R1,R2,R3,R4,R5,R6])
\end{python}

然后将矩阵 A0 设为邻接矩阵。
然后从矩阵 A0 计算矩阵 A1, 从矩阵 A1 计算矩阵 A2, 以此类推，最后计算矩阵 A6. 

\begin{python}
A0=W
A1=np.zeros_like(A0)
for i in range(6):
    for j in range(6):
        A1[i,j]=np.min([A0[i,j],A0[i,0]+A0[0,j]])

A2=np.zeros_like(A0)
for i in range(6):
    for j in range(6):
        A2[i,j]=np.min([A1[i,j],A1[i,1]+A1[1,j]])

A3=np.zeros_like(A0)
for i in range(6):
    for j in range(6):
        A3[i,j]=np.min([A2[i,j],A2[i,2]+A2[2,j]])

A4=np.zeros_like(A0)
for i in range(6):
    for j in range(6):
        A4[i,j]=np.min([A3[i,j],A3[i,3]+A3[3,j]])

A5=np.zeros_like(A0)
for i in range(6):
    for j in range(6):
        A5[i,j]=np.min([A4[i,j],A4[i,4]+A4[4,j]])

A6=np.zeros_like(A0)
for i in range(6):
    for j in range(6):
        A6[i,j]=np.min([A5[i,j],A5[i,3]+A5[3,j]])
\end{python}

也可以使用下述循环，简化上述迭代的代码。
\begin{python}
A=np.zeros([7,6,6])
A[0,:,:]=W
for k in range(1,7):
    for i in range(6):
        for j in range(6):
            A[k,i,j]=np.min([A[k-1,i,j],A[k-1,i,k-1]+A[k-1,k-1,j]])
\end{python}

这样我们得到矩阵 A6, 这是六个村庄的两两之间的最短距离。
\begin{eqnarray}
A_6= \begin{pmatrix}
0&2&6&7&8&11 \\ 
2&0&4&5&6&9 \\ 
6&4&0&1&2&5 \\ 
7&5&1&0&1&4 \\ 
8&6&2&1&0&3 \\ 
11&9&5&4&3&0 \\ 
\end{pmatrix}. 
\end{eqnarray}

为了确定医院的位置，我们的标准是，距离医院最远的村庄，到达医院的距离要尽可能的短。
因此我们计算矩阵 A6 的每一列的最大值。
\begin{python}
x=np.max(A6,axis=0)
\end{python}
得到结果是 
\begin{eqnarray}
x= \begin{pmatrix}
11&9&6&7&8&11 \\ 
\end{pmatrix}. 
\end{eqnarray}
因此第三个村庄是最合适的，第三个村庄到第一、二、四、五、六个村庄的最短距离分别为 6,4,1,2,5. 
自动识别第三个村庄可以使用下述代码。
\begin{python}
hospital=np.sum((x==min(x))*range(6))
print(hospital)
##the first question is answered: v=v3
\end{python}

为了确定学校的位置，我们的标准是，所有小学生到达学校的总路程要尽可能的少。
我们计算矩阵 A6 与人数列向量的乘积，可得
\begin{eqnarray}
\begin{pmatrix}
0&2&6&7&8&11 \\ 
2&0&4&5&6&9 \\ 
6&4&0&1&2&5 \\ 
7&5&1&0&1&4 \\ 
8&6&2&1&0&3 \\ 
11&9&5&4&3&0 \\ 
\end{pmatrix}
\cdot 
\begin{pmatrix}
50 \\ 
40 \\
60 \\
20 \\ 
70 \\
90 \\
\end{pmatrix}
=
\begin{pmatrix}
2130 \\ 
1670 \\
1070 \\
1040 \\ 
1050 \\
1500 \\
\end{pmatrix}. 
\end{eqnarray}
由此可见，如果将学校建在第一个村庄，那么所有小学生的上学总路程为2130; 
如果将学校建在第二个村庄，那么所有小学生的上学总路程为1670; 等等。 
因此如果将学校建在第四个村庄，那么所有小学生的上学总路程为1040, 是这些总路程中的最小值。
计算的代码如下。
\begin{python}
y=np.array([50,40,60,20,70,90])
B=np.dot(A6,y)
print(B)
\end{python}
自动识别第四个村庄，可以使用如下代码。
\begin{python}
C=B==min(B)
school=np.sum(C*range(6))
print(school)
##the second question is answered: v=v4
\end{python}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{回答问题}

医院建在第三个村庄，可以使得最偏远的村庄到达医院的路程最短。
小学建在第四个村庄，可以使得所有小学生的上学总路程最短。



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{参考文献 }
\begin{thebibliography}{99}
\bibitem{sishoukui-2} 司守奎,孙玺菁. \emph{Python数学建模算法与应用}, 国防工业出版社. 2022年1月第1版. 
\bibitem{rosen-dm6}Kenneth H. Rosen 著, 袁崇义, 屈婉玲, 张桂芸等译. \emph{离散数学及其应用}, 机械工业出版社，2013年4月第1版。
\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


